 // 1、无头单向非循环链表实现
 public class SingleLinkedList {

    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;
     //头插法
     public void addFirst(int data) {
         ListNode node = new ListNode(data);
         node.next = head;
         head = node;
     }
     //尾插法
     public void addLast(int data) {
         ListNode node = new ListNode(data);
         if(head == null) {
             head = node;
             return;
         }
         ListNode cur = head;
         while(cur.next != null) {
             cur = cur.next;
         }
         cur.next = node;
     }
     //任意位置插入,第一个数据节点为0号下标
     public void addIndex(int index,int data) {
         ListNode node = new ListNode(data);
         if(index < 0 || index > size()) {
             throw new IndexOutOfException("插入位置时, index不合法, 此时, index: " + index);
         }
         if(index == 0) {
             addFirst(data);
             return;
         }
         if(index == size()) {
             addLast(data);
             return;
         }
         ListNode cur = findIndexPre(index,head);
         node.next = cur.next;
         cur.next = node;
     }
     private ListNode findIndexPre(int index, ListNode node) {
         ListNode cur = node;
         while(index - 1 != 0) {
             cur = cur.next;
             index--;
         }
         return cur;
     }

     //查找是否包含关键字key是否在单链表当中
     public boolean contains(int key) {
         ListNode cur = head;
         while(cur != null) {
             if(cur.val == key) {
                 return true;
             }
             cur = cur.next;
         }
         return false;
     }
     //删除第一次出现关键字为key的节点
     public void remove(int key) {
         if(head == null) {
             System.out.println("没有你要删除的节点! ");
             return;
         }
         if(head.val == key) {
             head = head.next;
             return;
         }
         ListNode pre = head;
         ListNode cur = head.next;
         while(cur != null) {
             if(cur.val == key) {
                 pre.next = cur.next;
                 return;
             }else {
                 cur = cur.next;
                 pre = pre.next;

             }
         }
     }

     //删除所有值为key的节点
     public void removeAllKey(int key) {
         if(head == null) {
             System.out.println("单链表为空, 没有你要删除的节点");
             return;
         }
         ListNode cur = head.next;
         ListNode pre = head;
         while(cur != null) {
             if(cur.val == key) {
                 pre.next = cur.next;
                 cur = cur.next;
             }else {
                 pre = pre.next;
                 cur = cur.next;
             }
         }
         if(head.val == key) {
             head = head.next;
         }
     }
     //得到单链表的长度
     public int size() {
         ListNode cur = head;
         int count = 0;
         while(cur != null) {
             count++;
             cur = cur.next;
         }
         return count;
     }
     public void display() {
         ListNode cur = head;
         while(cur != null) {
             System.out.print(cur.val + " ");
             cur = cur.next;
         }
         System.out.println();
     }
     public void display(ListNode newHead) {
         ListNode cur = newHead;
         while(cur != null) {
             System.out.print(cur.val + " ");
             cur = cur.next;
         }
         System.out.println();
     }

     public void clear() {
         // this.head = null;

         while(head != null) {
             ListNode headNext = head.next;
             head.next = null;
             head = headNext;
         }
     }

     public ListNode reverseList() {
         if(head == null) {
             return null;
         }
         if(head.next == null) {
             return head;
         }
         ListNode cur = head.next;
         head.next = null;
         while(cur != null) {
             ListNode curNext = cur.next;
             cur.next = head;
             head = cur;
             cur = curNext;
         }
         return head;
     }

     public ListNode middleNode(ListNode head) {
         if(head == null) {
             return null;
         }
         if(head.next == null) {
             return head;
         }
         ListNode fast = head;
         ListNode slow = head;
         while(fast != null && fast.next != null) {
             fast = fast.next.next;
             slow = slow.next;
         }
         return slow;
     }

     public ListNode findKthToTail(int k) {
         if(k <= 0) {
             return null;
         }
         ListNode fast = head;
         ListNode slow = head;
         //1. 先让fast指针先走
         while(k - 1 != 0) {
             fast = fast.next;
             if(fast == null) {
                 return null;
             }
             k--;
         }
         //2. 然后fast和slow一起走
         while(fast.next != null) {
             fast = fast.next;
             slow = slow.next;
         }
         return slow;
     }

     public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
         ListNode newHead = new ListNode(-1);
         ListNode head = newHead;
         while(list1 != null && list2 != null) {
             if(list1.val < list2.val) {
                 head.next = list1;
                 head = list1;
                 list1 = list1.next;
             }else{
                 head.next = list2;
                 head = list2;
                 list2 = list2.next;
             }
         }
         if(list1 == null) {
             head.next = list2;
         }
         if(list2 == null) {
             head.next = list1;
         }
         return newHead.next;
     }

     public ListNode partition1(int x) {
         ListNode cur = head;
         ListNode as = null;
         ListNode ae = null;
         ListNode bs = null;
         ListNode be = null;
         while(cur != null) {
             if(cur.val > x ) {
                 if(as == null) {
                     as = cur;
                     ae = cur;
                     // cur = cur.next; 省略1 因为if else 都要走这个语句 所以可以省略
                 }else {
                     ae.next = cur;
                     ae = cur;
                     // cur = cur.next; 省略1 因为if else 都要走这个语句 所以可以省略
                 }
                 // cur = cur.next; // 省略2 因为if else 都要走这个语句 所以可以省略
             }else {
                 if(bs == null) {
                     bs = cur;
                     be = cur;
                     // cur = cur.next;  省略1 因为if else 都要走这个语句 所以可以省略
                 }else {
                     be.next = cur;
                     be = cur;
                     // cur = cur.next;  省略1 因为if else 都要走这个语句 所以可以省略
                 }
                 //cur = cur.next;   省略2 因为if else 都要走这个语句 所以可以省略
             }
             cur = cur.next;
         }
         // 难道两个段中 都会有数据吗?
         if(bs == null) {
             return as;
         }
         be.next = as;
         if(as != null) {
             ae.next = null;
         }
         return bs;
     }

     public ListNode partition( int x) {
         // write code here
         ListNode bs = null;
         ListNode be = null;
         ListNode as = null;
         ListNode ae = null;
         ListNode cur = head;
         while (cur != null) {
             if(cur.val < x) {
                 if(bs == null) {
                     bs = cur;
                     be = cur;
                     //cur = cur.next;省略1
                 }else {
                     be.next = cur;
                     be = cur;
                     //cur = cur.next;省略1
                 }
                 //cur = cur.next; 省略2
             }else {
                 //第一次插入的时候
                 if(as == null) {
                     as = cur;
                     ae = cur;
                     //cur = cur.next;省略1
                 }else {
                     ae.next = cur;
                     ae = cur;
                     //cur = cur.next;省略1
                 }
                 //cur = cur.next;省略2
             }
             cur = cur.next;
         }
         //要考虑： 难道2个段当中 都有数据吗？
         // 第一个段没有数据 直接返回第2个段！！
         if(bs == null) {
             return as;
         }
         be.next = as;
         if(as != null) {
             ae.next = null;
         }
         return bs;
     }
     public boolean chkPalindrome() {
         if(head == null) {
             return false;
         }
         ListNode fast = head;
         ListNode slow = head;
         // 1. 找中间节点
         while(fast != null && fast.next != null) {
             fast = fast.next.next;
             slow = slow.next;
         }
         // 2. 逆置单链表
         ListNode cur = slow.next;
         while(cur != null) {
             ListNode curNext = cur.next;
             cur.next = slow;
             slow = cur;
             cur = curNext;
         }
         //翻转成功
         // 3. 开始判断是否魏回文
         while(head != slow) {
             if(head.val != slow.val) {
                 return false;
             }
             // 判断偶数个节点时
             if(head.next == slow) {
                 return true;
             }
             head = head.next;
             slow = slow.next;
         }
         return true;
     }


     public static void main(String[] args) {
         SingleLinkedList singleLinkedList1 = new SingleLinkedList();
         //singleLinkedList.addFirst(1);
         singleLinkedList1.addLast(351);
         singleLinkedList1.addLast(5);
         singleLinkedList1.addLast(6);
         singleLinkedList1.addLast(90);
         singleLinkedList1.addLast(76);

         singleLinkedList1.display();
         SingleLinkedList.ListNode ret = singleLinkedList1.partition1(28);
         singleLinkedList1.display(ret);

        /* SingleLinkedList singleLinkedList2 = new SingleLinkedList();
         //singleLinkedList.addFirst(1);
         singleLinkedList2.addLast(1);
         singleLinkedList2.addLast(54);
         singleLinkedList2.addLast(85);
         singleLinkedList2.addLast(87);
         singleLinkedList2.addLast(99);*/


         /*singleLinkedList2.display();
         SingleLinkedList.ListNode ret2 =  singleLinkedList1.mergeTwoLists(singleLinkedList1.head,singleLinkedList2.head);
         singleLinkedList1.display(ret2);*/


        /* SingleLinkedList.ListNode ret = singleLinkedList1.findKthToTail(2);
         System.out.println(ret.val);*/

         //singleLinkedList.remove(5);
         //singleLinkedList.addIndex(3,0);
         //singleLinkedList.removeAllKey(1);


         /*SingleLinkedList.ListNode ret = singleLinkedList.middleNode();
         singleLinkedList.display(ret);*/
         //singleLinkedList.reverseList();
         //SingleLinkedList.ListNode ret = singleLinkedList.reverseList();
         //singleLinkedList.display();
         // System.out.println(singleLinkedList.size());
         //System.out.println(singleLinkedList.contains(2));
     }
 }